package com.lihepeng.leecode.slip_window;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 *  
 *
 * 注意：
 *
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-window-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution76 {
    Map<Character,Integer> ori = new HashMap<>();
    Map<Character,Integer> cnt = new HashMap<>();

    public String minWindow(String s, String t) {
        int tLength = t.length();
        for (int i=0;i<tLength;i++) {
            ori.put(t.charAt(i),ori.getOrDefault(t.charAt(i),0)+1);
        }
        int l = 0,r =-1;
        int len = Integer.MAX_VALUE,ansL = -1,ansR = -1;
        int sLen = s.length();
        while(r <sLen) {
            ++r;
            if (r <sLen && ori.containsKey(s.charAt(r))) {
                // 扩张
                cnt.put(s.charAt(r),cnt.getOrDefault(s.charAt(r),0)+1);
            }
            while (check() && l<=r) {
                // 收缩
                if (r-l +1 <len) {
                    len = r-l+1;
                    ansL = l;
                    ansR = l+len;
                }
                if (ori.containsKey(s.charAt(l))) {
                    cnt.put(s.charAt(l),cnt.getOrDefault(s.charAt(l),0)-1);
                }
                ++l;
            }
        }
        return  ansL ==-1?"":s.substring(ansL,ansR);
    }

    public String minWindow1(String s, String t) {
        if (s ==null || t ==null) {
            return null;
        }
        int [] needs = new int[128];
        // 将t 中的全部数据维护到needs
        for (int i=0;i<t.length() ;i++) {
            needs[s.charAt(i)]++;
        }
        int left =0;
        int right=0;




        return "";

    }

    private boolean check(){
        Iterator<Map.Entry<Character, Integer>> iterator = ori.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Character, Integer> next = iterator.next();
            Character key = next.getKey();
            Integer value = next.getValue();
            if (cnt.getOrDefault(key,0)<value) {
                return false;
            }
        }
        return true;
    }


}
